class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedListAlgorithms:
    @staticmethod
    def slow_fast_pointer(head):
        """
        快慢指针算法

        参数:
        head (ListNode): 链表的头节点

        返回:
        ListNode: 链表中间节点的引用

        实现步骤:
        1. 使用快慢指针，初始时快指针和慢指针都指向头节点
        2. 快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表尾部
        3. 返回慢指针所指向的节点，即为链表的中间节点

        """

        # 步骤 1: 使用快慢指针，初始时快指针和慢指针都指向头节点
        slow = head
        fast = head

        # 步骤 2: 快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表尾部
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 步骤 3: 返回慢指针所指向的节点，即为链表的中间节点
        return slow

    @staticmethod
    def reverse_linked_list(head):
        """
        反转链表算法

        参数:
        head (ListNode): 链表的头节点

        返回:
        ListNode: 反转后的链表头节点

        实现步骤:
        1. 定义三个指针prev, curr, next，初始时prev为None，curr为头节点
        2. 遍历链表，每次将当前节点的next指针指向前一个节点，然后更新prev、curr和next指针
        3. 当遍历完链表时，prev即为反转后的链表头节点

        """

        # 步骤 1: 定义三个指针prev, curr, next，初始时prev为None，curr为头节点
        prev = None
        curr = head

        # 步骤 2: 遍历链表，每次将当前节点的next指针指向前一个节点，然后更新prev、curr和next指针
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        # 步骤 3: 当遍历完链表时，prev即为反转后的链表头节点
        return prev

    @staticmethod
    def merge_lists(l1, l2):
        """
        链表合并算法

        参数:
        l1 (ListNode): 第一个链表的头节点
        l2 (ListNode): 第二个链表的头节点

        返回:
        ListNode: 合并后的链表头节点

        实现步骤:
        1. 定义一个哨兵节点dummy，以及一个指针curr指向dummy
        2. 遍历两个链表，比较节点的值，将较小值的节点连接到curr的next指针上
        3. 遍历结束后，若某个链表还有剩余节点，将剩余节点直接连接到curr的next指针上
        4. 返回dummy.next，即为合并后的链表头节点

        """

        # 步骤 1: 定义一个哨兵节点dummy，以及一个指针curr指向dummy
        dummy = ListNode(0)
        curr = dummy

        # 步骤 2: 遍历两个链表，比较节点的值，将较小值的节点连接到curr的next指针上
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next

        # 步骤 3: 遍历结束后，若某个链表还有剩余节点，将剩余节点直接连接到curr的next指针上
        if l1:
            curr.next = l1
        if l2:
            curr.next = l2

        # 步骤 4: 返回dummy.next，即为合并后的链表头节点
        return dummy.next

if __name__ == '__main__':
    # 示例数据
    # 链表1: 1 -> 2 -> 3 -> 4 -> 5
    head1 = ListNode(1)
    head1.next = ListNode(2)
    head1.next.next = ListNode(3)
    head1.next.next.next = ListNode(4)
    head1.next.next.next.next = ListNode(5)

    # 链表2: 6 -> 7 -> 8 -> 9 -> 10
    head2 = ListNode(6)
    head2.next = ListNode(7)
    head2.next.next = ListNode(8)
    head2.next.next.next = ListNode(9)
    head2.next.next.next.next = ListNode(10)

    # 示例调用快慢指针算法
    middle_node = LinkedListAlgorithms.slow_fast_pointer(head1)
    print("快慢指针算法输出:", middle_node.val)
    """
    示例输出结果:
    快慢指针算法输出: 3
    """

    # 示例调用反转链表算法
    reversed_head = LinkedListAlgorithms.reverse_linked_list(head1)
    curr = reversed_head
    reversed_list = []
    while curr:
        reversed_list.append(curr.val)
        curr = curr.next
    print("反转链表算法输出:", reversed_list)
    """
    示例输出结果:
    反转链表算法输出: [5, 4, 3, 2, 1]
    """

    # 示例调用链表合并算法
    merged_head = LinkedListAlgorithms.merge_lists(head1, head2)
    curr = merged_head
    merged_list = []
    while curr:
        merged_list.append(curr.val)
        curr = curr.next
    print("链表合并算法输出:", merged_list)
    """
    示例输出结果:
    链表合并算法输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    """
